'''
拓扑排序。在有向图中
    根据入度，排序，就是 a->b     a一定比b先弹出
'''
from collections import deque
from typing import List


def topological_sort(num_vertices, edges) -> List[List[int]]:
    # 邻接表建 有向图
    table = [[] for _ in range(num_vertices)]
    # 入度表
    indegrees = [0 for _ in range(num_vertices)]
    for u, v in edges:
        table[u].append(v)
        indegrees[v] += 1       # v的入度+1

    q = deque()     # 先进先出，比如右进左出
    for i, indegree in enumerate(indegrees):
        if indegree == 0:
            q.append(i)
    res = []
    while q:
        u = q.popleft()
        for v in table[u]:
            indegrees[v] -= 1
            if indegrees[v] == 0:
                q.append(v)
        res.append(u)
    return res if len(res) == num_vertices else []